package com.nulldev.util.data.Arrays.maps.trie;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Field;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

import com.nulldev.util.VariableAPI.MathUtil;
import com.nulldev.util.data.Arrays.maps.trie.base.None;
import com.nulldev.util.data.Arrays.maps.trie.base.Option;
import com.nulldev.util.data.Arrays.maps.trie.base.Some;

@SuppressWarnings(
	{ "unchecked", "rawtypes", "unused" })
public class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {
	private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class,
			"root");
	private static final long serialVersionUID = 1L;
	private static final Field READONLY_FIELD;

	static {
		final Field f;
		try {
			f = TrieMap.class.getDeclaredField("readOnly");
		} catch (NoSuchFieldException e) {
			throw new ExceptionInInitializerError(e);
		} catch (SecurityException e) {
			throw new ExceptionInInitializerError(e);
		}
		f.setAccessible(true);
		READONLY_FIELD = f;
	}

	/**
	 * EntrySet
	 */
	private transient final EntrySet entrySet = new EntrySet();

	public static <K, V> TrieMap<K, V> empty() {
		return new TrieMap<K, V>();
	}

	// static class MangledHashing<K> extends Hashing<K> {
	// int hash(K k) {
	// return util.hashing.byteswap32(k);
	// }
	// }

	static class INode<K, V> extends INodeBase<K, V> {
		static final Object KEY_PRESENT = new Object();
		static final Object KEY_ABSENT = new Object();

		static <K, V> INode<K, V> newRootNode() {
			Gen gen = new Gen();
			CNode<K, V> cn = new CNode<K, V>(0, new BasicNode[]
				{}, gen);
			return new INode<K, V>(cn, gen);
		}

		public INode(MainNode<K, V> bn, Gen g) {
			super(g);
			WRITE(bn);
		}

		public INode(Gen g) {
			this(null, g);
		}

		final void WRITE(final MainNode<K, V> nval) {
			INodeBase.updater.set(this, nval);
		}

		final boolean CAS(final MainNode<K, V> old, final MainNode<K, V> n) {
			return INodeBase.updater.compareAndSet(this, old, n);
		}

		final MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
			return GCAS_READ(ct);
		}

		final MainNode<K, V> GCAS_READ(TrieMap<K, V> ct) {
			MainNode<K, V> m = /* READ */mainnode;
			MainNode<K, V> prevval = /* READ */m.prev;
			if (prevval == null)
				return m;
			else
				return GCAS_Complete(m, ct);
		}

		private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
			while (true) {
				if (m == null)
					return null;
				else {
					// complete the GCAS
					MainNode<K, V> prev = /* READ */m.prev;
					INode<K, V> ctr = ct.readRoot(true);

					if (prev == null)
						return m;

					if (prev instanceof FailedNode) {
						// try to commit to previous value
						FailedNode<K, V> fn = (FailedNode<K, V>) prev;
						if (CAS(m, fn.prev))
							return fn.prev;
						else {
							// Tailrec
							// return GCAS_Complete (/* READ */mainnode, ct);
							m = /* READ */mainnode;
							continue;
						}
					} else {
						// Assume that you've read the root from the generation
						// G.
						// Assume that the snapshot algorithm is correct.
						// ==> you can only reach nodes in generations <= G.
						// ==> `gen` is <= G.
						// We know that `ctr.gen` is >= G.
						// ==> if `ctr.gen` = `gen` then they are both equal to
						// G.
						// ==> otherwise, we know that either `ctr.gen` > G,
						// `gen` <
						// G,
						// or both
						if ((ctr.gen == gen) && ct.nonReadOnly()) {
							// try to commit
							if (m.CAS_PREV(prev, null))
								return m;
							else {
								// return GCAS_Complete (m, ct);
								// tailrec
								continue;
							}
						} else {
							// try to abort
							m.CAS_PREV(prev, new FailedNode<K, V>(prev));
							return GCAS_Complete(/* READ */mainnode, ct);
						}
					}
				}
			}
		}

		final boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
			n.WRITE_PREV(old);
			if (CAS(old, n)) {
				GCAS_Complete(n, ct);
				return /* READ */n.prev == null;
			} else
				return false;
		}

		private boolean equal(final K k1, final K k2, final TrieMap<K, V> ct) {
			return ct.equality().equiv(k1, k2);
		}

		private INode<K, V> inode(final MainNode<K, V> cn) {
			INode<K, V> nin = new INode<K, V>(gen);
			nin.WRITE(cn);
			return nin;
		}

		final INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
			INode<K, V> nin = new INode<K, V>(ngen);
			MainNode<K, V> main = GCAS_READ(ct);
			nin.WRITE(main);
			return nin;
		}

		/**
		 * Inserts a key value pair, overwriting the old pair if the keys match.
		 * 
		 * @return true if successful, false otherwise
		 */
		final boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
			while (true) {
				MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!

				if (m instanceof CNode) {
					// 1) a multiway node
					CNode<K, V> cn = (CNode<K, V>) m;
					int idx = (hc >>> lev) & 0x1f;
					int flag = 1 << idx;
					int bmp = cn.bitmap;
					int mask = flag - 1;
					int pos = Integer.bitCount(bmp & mask);
					if ((bmp & flag) != 0) {
						// 1a) insert below
						BasicNode cnAtPos = cn.array[pos];
						if (cnAtPos instanceof INode) {
							INode<K, V> in = (INode<K, V>) cnAtPos;
							if (startgen == in.gen)
								return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
							else {
								if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
									// return rec_insert (k, v, hc, lev, parent,
									// startgen, ct);
									// tailrec
									continue;
								} else
									return false;
							}
						} else if (cnAtPos instanceof SNode) {
							SNode<K, V> sn = (SNode<K, V>) cnAtPos;
							if (sn.hc == hc && equal(sn.k, k, ct))
								return GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct);
							else {
								CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
								MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen);
								return GCAS(cn, nn, ct);
							}
						}
					} else {
						CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
						MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<K, V>(k, v, hc), gen);
						return GCAS(cn, ncnode, ct);
					}
				} else if (m instanceof TNode) {
					clean(parent, ct, lev - 5);
					return false;
				} else if (m instanceof LNode) {
					LNode<K, V> ln = (LNode<K, V>) m;
					MainNode<K, V> nn = ln.inserted(k, v);
					return GCAS(ln, nn, ct);
				}

				throw new RuntimeException("Should not happen");
			}
		}

		/**
		 * Inserts a new key value pair, given that a specific condition is met.
		 * 
		 * @param cond null - don't care if the key was there KEY_ABSENT - key wasn't
		 *             there KEY_PRESENT - key was there other value `v` - key must be
		 *             bound to `v`
		 * @return null if unsuccessful, Option[V] otherwise (indicating previous value
		 *         bound to the key)
		 */
		final Option<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev, final INode<K, V> parent, final Gen startgen,
				final TrieMap<K, V> ct) {
			while (true) {
				MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!

				if (m instanceof CNode) {
					// 1) a multiway node
					CNode<K, V> cn = (CNode<K, V>) m;
					int idx = (hc >>> lev) & 0x1f;
					int flag = 1 << idx;
					int bmp = cn.bitmap;
					int mask = flag - 1;
					int pos = Integer.bitCount(bmp & mask);

					if ((bmp & flag) != 0) {
						// 1a) insert below
						BasicNode cnAtPos = cn.array[pos];
						if (cnAtPos instanceof INode) {
							INode<K, V> in = (INode<K, V>) cnAtPos;
							if (startgen == in.gen)
								return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
							else {
								if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
									// return rec_insertif (k, v, hc, cond, lev,
									// parent, startgen, ct);
									// tailrec
									continue;
								} else
									return null;
							}
						} else if (cnAtPos instanceof SNode) {
							SNode<K, V> sn = (SNode<K, V>) cnAtPos;
							if (cond == null) {
								if (sn.hc == hc && equal(sn.k, k, ct)) {
									if (GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct))
										return Option.makeOption(sn.v);
									else
										return null;
								} else {
									CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
									MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen);
									if (GCAS(cn, nn, ct))
										return Option.makeOption(); // None;
									else
										return null;
								}

							} else if (cond == INode.KEY_ABSENT) {
								if (sn.hc == hc && equal(sn.k, k, ct))
									return Option.makeOption(sn.v);
								else {
									CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
									MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen);
									if (GCAS(cn, nn, ct))
										return Option.makeOption(); // None
									else
										return null;
								}
							} else if (cond == INode.KEY_PRESENT) {
								if (sn.hc == hc && equal(sn.k, k, ct)) {
									if (GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct))
										return Option.makeOption(sn.v);
									else
										return null;

								} else
									return Option.makeOption();// None;
							} else {
								if (sn.hc == hc && equal(sn.k, k, ct) && sn.v == cond) {
									if (GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct))
										return Option.makeOption(sn.v);
									else
										return null;
								} else
									return Option.makeOption(); // None
							}

						}
					} else if (cond == null || cond == INode.KEY_ABSENT) {
						CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
						CNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<K, V>(k, v, hc), gen);
						if (GCAS(cn, ncnode, ct))
							return Option.makeOption();// None
						else
							return null;
					} else if (cond == INode.KEY_PRESENT) {
						return Option.makeOption();// None;
					} else
						return Option.makeOption(); // None
				} else if (m instanceof TNode) {
					clean(parent, ct, lev - 5);
					return null;
				} else if (m instanceof LNode) {
					// 3) an l-node
					LNode<K, V> ln = (LNode<K, V>) m;
					if (cond == null) {
						Option<V> optv = ln.get(k);
						if (insertln(ln, k, v, ct))
							return optv;
						else
							return null;
					} else if (cond == INode.KEY_ABSENT) {
						Option<V> t = ln.get(k);
						if (t == null || t instanceof None) {
							if (insertln(ln, k, v, ct))
								return Option.makeOption();// None
							else
								return null;
						} else
							return t;
					} else if (cond == INode.KEY_PRESENT) {
						Option<V> t = ln.get(k);
						if (t != null) {
							if (insertln(ln, k, v, ct))
								return t;
							else
								return null;
						} else
							return null; // None
					} else {
						Option<V> t = ln.get(k);
						if (t != null) {
							if (((Some<V>) t).get() == cond) {
								if (insertln(ln, k, v, ct))
									return new Some<V>((V) cond);
								else
									return null;

							} else
								return Option.makeOption();
						}
					}
				}

//                throw new RuntimeException ("Should not happen");
			}
		}

		final boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
			LNode<K, V> nn = ln.inserted(k, v);
			return GCAS(ln, nn, ct);
		}

		/**
		 * Looks up the value associated with the key.
		 * 
		 * @return null if no value has been found, RESTART if the operation wasn't
		 *         successful, or any other value otherwise
		 */
		final Object rec_lookup(final K k, final int hc, int lev, INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
			while (true) {
				MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!

				if (m instanceof CNode) {
					// 1) a multinode
					final CNode<K, V> cn = (CNode<K, V>) m;
					int idx = (hc >>> lev) & 0x1f;
					int flag = 1 << idx;
					int bmp = cn.bitmap;
					if ((bmp & flag) == 0)
						return null; // 1a) bitmap shows no binding
					else { // 1b) bitmap contains a value - descend
						int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
						final BasicNode sub = cn.array[pos];
						if (sub instanceof INode) {
							INode<K, V> in = (INode<K, V>) sub;
							if (ct.isReadOnly() || (startgen == ((INodeBase<K, V>) sub).gen))
								return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
							else {
								if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
									// return rec_lookup (k, hc, lev, parent,
									// startgen, ct);
									// Tailrec
									continue;
								} else
									return RESTART; // used to be throw
													// RestartException
							}
						} else if (sub instanceof SNode) {
							// 2) singleton node
							SNode<K, V> sn = (SNode<K, V>) sub;
							if (((SNode) sub).hc == hc && equal(sn.k, k, ct))
								return sn.v;
							else
								return null;
						}
					}
				} else if (m instanceof TNode) {
					// 3) non-live node
					return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
				} else if (m instanceof LNode) {
					// 5) an l-node
					return ((LNode<K, V>) m).get(k);
				}

				throw new RuntimeException("Should not happen");
			}
		}

		private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct, K k, int hc) {
			if (ct.nonReadOnly()) {
				clean(parent, ct, lev - 5);
				return RESTART; // used to be throw RestartException
			} else {
				if (tn.hc == hc && equal(tn.k, k, ct))
					return tn.v;
				else
					return null;
			}
		}

		/**
		 * Removes the key associated with the given value.
		 * 
		 * @param v if null, will remove the key irregardless of the value; otherwise
		 *          removes only if binding contains that exact key and value
		 * @return null if not successful, an Option[V] indicating the previous value
		 *         otherwise
		 */
		final Option<V> rec_remove(K k, V v, int hc, int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
			MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!

			if (m instanceof CNode) {
				CNode<K, V> cn = (CNode<K, V>) m;
				int idx = (hc >>> lev) & 0x1f;
				int bmp = cn.bitmap;
				int flag = 1 << idx;
				if ((bmp & flag) == 0)
					return Option.makeOption();
				else {
					int pos = Integer.bitCount(bmp & (flag - 1));
					BasicNode sub = cn.array[pos];
					Option<V> res = null;
					if (sub instanceof INode) {
						INode<K, V> in = (INode<K, V>) sub;
						if (startgen == in.gen)
							res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
						else {
							if (GCAS(cn, cn.renewed(startgen, ct), ct))
								res = rec_remove(k, v, hc, lev, parent, startgen, ct);
						}

					} else if (sub instanceof SNode) {
						SNode<K, V> sn = (SNode<K, V>) sub;
						if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
							MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
							if (GCAS(cn, ncn, ct))
								res = Option.makeOption(sn.v);
						} else
							res = Option.makeOption();
					}

					if (res instanceof None || (res == null))
						return res;
					else {
						if (parent != null) { // never tomb at root
							MainNode<K, V> n = GCAS_READ(ct);
							if (n instanceof TNode)
								cleanParent(n, parent, ct, hc, lev, startgen);
						}

						return res;
					}
				}
			} else if (m instanceof TNode) {
				clean(parent, ct, lev - 5);
				return null;
			} else if (m instanceof LNode) {
				LNode<K, V> ln = (LNode<K, V>) m;
				if (v == null) {
					Option<V> optv = ln.get(k);
					MainNode<K, V> nn = ln.removed(k, ct);
					if (GCAS(ln, nn, ct))
						return optv;
					else
						return null;
				} else {
					Option<V> tmp = ln.get(k);
					if (tmp instanceof Some) {
						Some<V> tmp1 = (Some<V>) tmp;
						if (tmp1.get() == v) {
							MainNode<K, V> nn = ln.removed(k, ct);
							if (GCAS(ln, nn, ct))
								return tmp;
							else
								return null;
						}
					}
				}
			}
			throw new RuntimeException("Should not happen");
		}

		void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc, final int lev, final Gen startgen) {
			while (true) {
				MainNode<K, V> pm = parent.GCAS_READ(ct);
				if (pm instanceof CNode) {
					CNode<K, V> cn = (CNode<K, V>) pm;
					int idx = (hc >>> (lev - 5)) & 0x1f;
					int bmp = cn.bitmap;
					int flag = 1 << idx;
					if ((bmp & flag) == 0) {
					} // somebody already removed this i-node, we're done
					else {
						int pos = Integer.bitCount(bmp & (flag - 1));
						BasicNode sub = cn.array[pos];
						if (sub == this) {
							if (nonlive instanceof TNode) {
								TNode<K, V> tn = (TNode<K, V>) nonlive;
								MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
								if (!parent.GCAS(cn, ncn, ct))
									if (ct.readRoot().gen == startgen) {
										// cleanParent (nonlive, parent, ct, hc,
										// lev, startgen);
										// tailrec
										continue;
									}
							}
						}
					}
				} else {
					// parent is no longer a cnode, we're done
				}
				break;
			}
		}

		private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, int lev) {
			MainNode<K, V> m = nd.GCAS_READ(ct);
			if (m instanceof CNode) {
				CNode<K, V> cn = (CNode<K, V>) m;
				nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
			}
		}

		final boolean isNullInode(final TrieMap<K, V> ct) {
			return GCAS_READ(ct) == null;
		}

		final int cachedSize(final TrieMap<K, V> ct) {
			MainNode<K, V> m = GCAS_READ(ct);
			return m.cachedSize(ct);
		}

		// /* this is a quiescent method! */
		// def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
		// match {
		// case null => "<null>"
		// case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
		// tn.hc)
		// case cn: CNode[_, _] => cn.string(lev)
		// case ln: LNode[_, _] => ln.string(lev)
		// case x => "<elem: %s>".format(x)
		// })

		public String string(int lev) {
			return "INode";
		}

	}

	private static final class FailedNode<K, V> extends MainNode<K, V> {
		final MainNode<K, V> p;

		FailedNode(final MainNode<K, V> p) {
			this.p = p;
			WRITE_PREV(p);
		}

		public String string(int lev) {
			throw new UnsupportedOperationException();
		}

		public int cachedSize(Object ct) {
			throw new UnsupportedOperationException();
		}

		public String toString() {
			return String.format("FailedNode(%s)", p);
		}
	}

	private interface KVNode<K, V> {
		Map.Entry<K, V> kvPair();
	}

	private static final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
		final K k;
		final V v;
		final int hc;

		SNode(final K k, final V v, final int hc) {
			this.k = k;
			this.v = v;
			this.hc = hc;
		}

		final SNode<K, V> copy() {
			return new SNode<K, V>(k, v, hc);
		}

		final TNode<K, V> copyTombed() {
			return new TNode<K, V>(k, v, hc);
		}

		final SNode<K, V> copyUntombed() {
			return new SNode<K, V>(k, v, hc);
		}

		final public Map.Entry<K, V> kvPair() {
			return new SimpleImmutableEntry<K, V>(k, v);
		}

		final public String string(int lev) {
			// (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
			return "SNode";
		}
	}

	private static final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
		final K k;
		final V v;
		final int hc;

		TNode(final K k, final V v, final int hc) {
			this.k = k;
			this.v = v;
			this.hc = hc;
		}

		final TNode<K, V> copy() {
			return new TNode<K, V>(k, v, hc);
		}

		final TNode<K, V> copyTombed() {
			return new TNode<K, V>(k, v, hc);
		}

		final SNode<K, V> copyUntombed() {
			return new SNode<K, V>(k, v, hc);
		}

		final public Entry<K, V> kvPair() {
			return new SimpleImmutableEntry<K, V>(k, v);
		}

		final public int cachedSize(Object ct) {
			return 1;
		}

		final public String string(int lev) {
			// (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
			return "TNode";
		}
	}

	private final static class LNode<K, V> extends MainNode<K, V> {
		final ListMap<K, V> listmap;

		public LNode(final ListMap<K, V> listmap) {
			this.listmap = listmap;
		}

		public LNode(K k, V v) {
			this(ListMap.map(k, v));
		}

		public LNode(K k1, V v1, K k2, V v2) {
			this(ListMap.map(k1, v1, k2, v2));
		}

		LNode<K, V> inserted(K k, V v) {
			return new LNode<K, V>(listmap.add(k, v));
		}

		MainNode<K, V> removed(K k, final TrieMap<K, V> ct) {
			ListMap<K, V> updmap = listmap.remove(k);
			if (updmap.size() > 1)
				return new LNode<K, V>(updmap);
			else {
				Entry<K, V> kv = updmap.iterator().next();
				// create it tombed so that it gets compressed on subsequent
				// accesses
				return new TNode<K, V>(kv.getKey(), kv.getValue(), ct.computeHash(kv.getKey()));
			}
		}

		Option<V> get(K k) {
			return listmap.get(k);
		}

		public int cachedSize(Object ct) {
			return listmap.size();
		}

		public String string(int lev) {
			// (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
			return "LNode";
		}
	}

	private static final class CNode<K, V> extends CNodeBase<K, V> {

		final int bitmap;
		final BasicNode[] array;
		final Gen gen;

		CNode(final int bitmap, final BasicNode[] array, final Gen gen) {
			this.bitmap = bitmap;
			this.array = array;
			this.gen = gen;
		}

		// this should only be called from within read-only snapshots
		final public int cachedSize(Object ct) {
			int currsz = READ_SIZE();
			if (currsz != -1)
				return currsz;
			else {
				int sz = computeSize((TrieMap<K, V>) ct);
				while (READ_SIZE() == -1)
					CAS_SIZE(-1, sz);
				return READ_SIZE();
			}
		}

		// lends itself towards being parallelizable by choosing
		// a random starting offset in the array
		// => if there are concurrent size computations, they start
		// at different positions, so they are more likely to
		// to be independent
		private int computeSize(final TrieMap<K, V> ct) {
			int i = 0;
			int sz = 0;
			final int offset = (array.length > 0) ? ThreadLocalRandom.current().nextInt(0, array.length) : 0;
			while (i < array.length) {
				int pos = (i + offset) % array.length;
				BasicNode elem = array[pos];
				if (elem instanceof SNode)
					sz += 1;
				else if (elem instanceof INode)
					sz += ((INode<K, V>) elem).cachedSize(ct);
				i += 1;
			}
			return sz;
		}

		final CNode<K, V> updatedAt(int pos, final BasicNode nn, final Gen gen) {
			BasicNode[] narr = array.clone();
			narr[pos] = nn;
			return new CNode<K, V>(bitmap, narr, gen);
		}

		final CNode<K, V> removedAt(int pos, int flag, final Gen gen) {
			BasicNode[] arr = array;
			int len = arr.length;
			BasicNode[] narr = new BasicNode[len - 1];
			System.arraycopy(arr, 0, narr, 0, pos);
			System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
			return new CNode<K, V>(bitmap ^ flag, narr, gen);
		}

		final CNode<K, V> insertedAt(int pos, int flag, final BasicNode nn, final Gen gen) {
			int len = array.length;
			int bmp = bitmap;
			BasicNode[] narr = new BasicNode[len + 1];
			System.arraycopy(array, 0, narr, 0, pos);
			narr[pos] = nn;
			System.arraycopy(array, pos, narr, pos + 1, len - pos);
			return new CNode<K, V>(bmp | flag, narr, gen);
		}

		/**
		 * Returns a copy of this cnode such that all the i-nodes below it are copied to
		 * the specified generation `ngen`.
		 */
		final CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
			int i = 0;
			BasicNode[] arr = array;
			int len = arr.length;
			BasicNode[] narr = new BasicNode[len];
			while (i < len) {
				BasicNode elem = arr[i];
				if (elem instanceof INode) {
					INode<K, V> in = (INode<K, V>) elem;
					narr[i] = in.copyToGen(ngen, ct);
				} else
					narr[i] = elem;
				i += 1;
			}
			return new CNode<K, V>(bitmap, narr, ngen);
		}

		private BasicNode resurrect(final INode<K, V> inode, final Object inodemain) {
			if (inodemain instanceof TNode) {
				TNode<K, V> tn = (TNode<K, V>) inodemain;
				return tn.copyUntombed();
			} else
				return inode;
		}

		final MainNode<K, V> toContracted(int lev) {
			if (array.length == 1 && lev > 0) {
				if (array[0] instanceof SNode) {
					SNode<K, V> sn = (SNode<K, V>) array[0];
					return sn.copyTombed();
				} else
					return this;

			} else
				return this;
		}

		// - if the branching factor is 1 for this CNode, and the child
		// is a tombed SNode, returns its tombed version
		// - otherwise, if there is at least one non-null node below,
		// returns the version of this node with at least some null-inodes
		// removed (those existing when the op began)
		// - if there are only null-i-nodes below, returns null
		final MainNode<K, V> toCompressed(final TrieMap<K, V> ct, int lev, Gen gen) {
			int bmp = bitmap;
			int i = 0;
			BasicNode[] arr = array;
			BasicNode[] tmparray = new BasicNode[arr.length];
			while (i < arr.length) { // construct new bitmap
				BasicNode sub = arr[i];
				if (sub instanceof INode) {
					INode<K, V> in = (INode<K, V>) sub;
					MainNode<K, V> inodemain = in.gcasRead(ct);
					assert (inodemain != null);
					tmparray[i] = resurrect(in, inodemain);
				} else if (sub instanceof SNode) {
					tmparray[i] = sub;
				}
				i += 1;
			}

			return new CNode<K, V>(bmp, tmparray, gen).toContracted(lev);
		}

		public String string(int lev) {
			// "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
			// 1)).mkString("\n"));
			return "CNode";
		}

		/*
		 * quiescently consistent - don't call concurrently to anything involving a
		 * GCAS!!
		 */
		// protected Seq<K,V> collectElems() {
		// array flatMap {
		// case sn: SNode[K, V] => Some(sn.kvPair)
		// case in: INode[K, V] => in.mainnode match {
		// case tn: TNode[K, V] => Some(tn.kvPair)
		// case ln: LNode[K, V] => ln.listmap.toList
		// case cn: CNode[K, V] => cn.collectElems
		// }
		// }
		// }

		// protected Seq<String> collectLocalElems() {
		// // array flatMap {
		// // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
		// // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
		// ")")
		// // }
		// return null;
		// }

		public String toString() {
			// val elems = collectLocalElems
			// "CNode(sz: %d; %s)".format(elems.size,
			// elems.sorted.mkString(", "))
			return "CNode";
		}

		static <K, V> MainNode<K, V> dual(final SNode<K, V> x, int xhc, final SNode<K, V> y, int yhc, int lev, Gen gen) {
			if (lev < 35) {
				int xidx = (xhc >>> lev) & 0x1f;
				int yidx = (yhc >>> lev) & 0x1f;
				int bmp = (1 << xidx) | (1 << yidx);

				if (xidx == yidx) {
					INode<K, V> subinode = new INode<K, V>(gen);// (TrieMap.inodeupdater)
					subinode.mainnode = dual(x, xhc, y, yhc, lev + 5, gen);
					return new CNode<K, V>(bmp, new BasicNode[]
						{ subinode }, gen);
				} else {
					if (xidx < yidx)
						return new CNode<K, V>(bmp, new BasicNode[]
							{ x, y }, gen);
					else
						return new CNode<K, V>(bmp, new BasicNode[]
							{ y, x }, gen);
				}
			} else {
				return new LNode<K, V>(x.k, x.v, y.k, y.v);
			}
		}

	}

	private static class RDCSS_Descriptor<K, V> {
		INode<K, V> old;
		MainNode<K, V> expectedmain;
		INode<K, V> nv;
		volatile boolean committed = false;

		public RDCSS_Descriptor(final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
			this.old = old;
			this.expectedmain = expectedmain;
			this.nv = nv;
		}

	}

	private static class Equiv<K> implements Serializable {
		private static final long serialVersionUID = 1L;

		public boolean equiv(K k1, K k2) {
			return k1.equals(k2);
		}

		static final Equiv universal = new Equiv();
	}

	private static interface Hashing<K> extends Serializable {
		public int hash(K k);
	}

	static class Default<K> implements Hashing<K> {
		private static final long serialVersionUID = 1L;

		public int hash(K k) {
			if (k == null)
				return 0;
			int h = k.hashCode();
			// This function ensures that hashCodes that differ only by
			// constant multiples at each bit position have a bounded
			// number of collisions (approximately 8 at default load factor).
			h ^= (h >>> 20) ^ (h >>> 12);
			h ^= (h >>> 7) ^ (h >>> 4);
			return h;
		}

		static final Default instance = new Default();
	}

	private final Hashing<K> hashingobj;
	private final Equiv<K> equalityobj;

	Hashing<K> hashing() {
		return hashingobj;
	}

	Equiv<K> equality() {
		return equalityobj;
	}

	private transient volatile Object root;
	private final transient boolean readOnly;

	TrieMap(final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
		this.hashingobj = hashf;
		this.equalityobj = ef;
		this.readOnly = readOnly;
	}

	TrieMap(final Object r, final Hashing<K> hashf, final Equiv<K> ef, boolean readOnly) {
		this(hashf, ef, readOnly);
		this.root = r;
	}

	public TrieMap(final Hashing<K> hashf, final Equiv<K> ef) {
		this(INode.newRootNode(), hashf, ef, false);
	}

	public TrieMap() {
		this(Default.instance, Equiv.universal);
	}

	public TrieMap(final Map<K, V> map) {
		this(Default.instance, Equiv.universal);
		this.putAll(map);
	}

	/* internal methods */

	final boolean CAS_ROOT(Object ov, Object nv) {
		if (isReadOnly()) {
			throw new IllegalStateException("Attempted to modify a read-only snapshot");
		}
		return ROOT_UPDATER.compareAndSet(this, ov, nv);
	}

	// FIXME: abort = false by default
	final INode<K, V> readRoot(boolean abort) {
		return RDCSS_READ_ROOT(abort);
	}

	final INode<K, V> readRoot() {
		return RDCSS_READ_ROOT(false);
	}

	final INode<K, V> RDCSS_READ_ROOT() {
		return RDCSS_READ_ROOT(false);
	}

	final INode<K, V> RDCSS_READ_ROOT(boolean abort) {
		Object r = /* READ */root;
		if (r instanceof INode)
			return (INode<K, V>) r;
		else if (r instanceof RDCSS_Descriptor) {
			return RDCSS_Complete(abort);
		}
		throw new RuntimeException("Should not happen");
	}

	private final INode<K, V> RDCSS_Complete(final boolean abort) {
		while (true) {
			Object v = /* READ */root;
			if (v instanceof INode)
				return (INode<K, V>) v;
			else if (v instanceof RDCSS_Descriptor) {
				RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
				INode<K, V> ov = desc.old;
				MainNode<K, V> exp = desc.expectedmain;
				INode<K, V> nv = desc.nv;

				if (abort) {
					if (CAS_ROOT(desc, ov))
						return ov;
					else {
						// return RDCSS_Complete (abort);
						// tailrec
						continue;
					}
				} else {
					MainNode<K, V> oldmain = ov.gcasRead(this);
					if (oldmain == exp) {
						if (CAS_ROOT(desc, nv)) {
							desc.committed = true;
							return nv;
						} else {
							// return RDCSS_Complete (abort);
							// tailrec
							continue;
						}
					} else {
						if (CAS_ROOT(desc, ov))
							return ov;
						else {
							// return RDCSS_Complete (abort);
							// tailrec
							continue;

						}
					}
				}
			}

			throw new RuntimeException("Should not happen");
		}
	}

	private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
		RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<K, V>(ov, expectedmain, nv);
		if (CAS_ROOT(ov, desc)) {
			RDCSS_Complete(false);
			return /* READ */desc.committed;
		} else
			return false;
	}

	private void inserthc(final K k, final int hc, final V v) {
		while (true) {
			INode<K, V> r = RDCSS_READ_ROOT();
			if (!r.rec_insert(k, v, hc, 0, null, r.gen, this)) {
				// inserthc (k, hc, v);
				// tailrec
				continue;
			}
			break;
		}
	}

	private Option<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
		while (true) {
			INode<K, V> r = RDCSS_READ_ROOT();

			Option<V> ret = r.rec_insertif(k, v, hc, cond, 0, null, r.gen, this);
			if (ret == null) {
				// return insertifhc (k, hc, v, cond);
				// tailrec
				continue;
			} else
				return ret;
		}
	}

	private Object lookuphc(final K k, final int hc) {
		while (true) {
			INode<K, V> r = RDCSS_READ_ROOT();
			Object res = r.rec_lookup(k, hc, 0, null, r.gen, this);
			if (res == INodeBase.RESTART) {
				// return lookuphc (k, hc);
				// tailrec
				continue;
			} else
				return res;
		}
	}

	private Option<V> removehc(final K k, final V v, final int hc) {
		while (true) {
			INode<K, V> r = RDCSS_READ_ROOT();
			Option<V> res = r.rec_remove(k, v, hc, 0, null, r.gen, this);
			if (res != null)
				return res;
			else {
				// return removehc (k, v, hc);
				// tailrec
				continue;
			}
		}
	}

	/**
	 * Ensure this instance is read-write, throw UnsupportedOperationException
	 * otherwise. Used by Map-type methods for quick check.
	 */
	private void ensureReadWrite() {
		if (isReadOnly()) {
			throw new UnsupportedOperationException("Attempted to modify a read-only view");
		}
	}

	public String string() {
		// RDCSS_READ_ROOT().string(0);
		return "Root";
	}

	/* public methods */

	// public Seq<V> seq() {
	// return this;
	// }

	// override def par = new ParTrieMap(this)

	// static TrieMap empty() {
	// return new TrieMap();
	// }

	final boolean isReadOnly() {
		return readOnly;
	}

	final boolean nonReadOnly() {
		return !readOnly;
	}

	/**
	 * Returns a snapshot of this TrieMap. This operation is lock-free and
	 * linearizable.
	 * 
	 * The snapshot is lazily updated - the first time some branch in the snapshot
	 * or this TrieMap are accessed, they are rewritten. This means that the work of
	 * rebuilding both the snapshot and this TrieMap is distributed across all the
	 * threads doing updates or accesses subsequent to the snapshot creation.
	 */

	final public TrieMap<K, V> snapshot() {
		while (true) {
			INode<K, V> r = RDCSS_READ_ROOT();
			final MainNode<K, V> expmain = r.gcasRead(this);
			if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this)))
				return new TrieMap<K, V>(r.copyToGen(new Gen(), this), hashing(), equality(), readOnly);
			else {
				// return snapshot ();
				// tailrec
				continue;
			}
		}
	}

	/**
	 * Returns a read-only snapshot of this TrieMap. This operation is lock-free and
	 * linearizable.
	 * 
	 * The snapshot is lazily updated - the first time some branch of this TrieMap
	 * are accessed, it is rewritten. The work of creating the snapshot is thus
	 * distributed across subsequent updates and accesses on this TrieMap by all
	 * threads. Note that the snapshot itself is never rewritten unlike when calling
	 * the `snapshot` method, but the obtained snapshot cannot be modified.
	 * 
	 * This method is used by other methods such as `size` and `iterator`.
	 */
	final public TrieMap<K, V> readOnlySnapshot() {
		// Is it a snapshot of a read-only snapshot?
		if (!nonReadOnly())
			return this;

		while (true) {
			INode<K, V> r = RDCSS_READ_ROOT();
			MainNode<K, V> expmain = r.gcasRead(this);
			if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this)))
				return new TrieMap<K, V>(r, hashing(), equality(), true);
			else {
				// return readOnlySnapshot ();
				continue;
			}
		}
	}

	final public void clear() {
		while (true) {
			INode<K, V> r = RDCSS_READ_ROOT();
			if (!RDCSS_ROOT(r, r.gcasRead(this), INode.<K, V>newRootNode())) {
				continue;
			} else {
				return;
			}
		}
	}

	// @inline
	int computeHash(K k) {
		return hashingobj.hash(k);
	}

	final V lookup(K k) {
		int hc = computeHash(k);
//        return (V) lookuphc (k, hc);
		Object o = lookuphc(k, hc);
		if (o instanceof Some) {
			return ((Some<V>) o).get();
		} else if (o instanceof None)
			return null;
		else
			return (V) o;
	}

	final V apply(K k) {
		int hc = computeHash(k);
		Object res = lookuphc(k, hc);
		if (res == null)
			throw new NoSuchElementException();
		else
			return (V) res;
	}

//    final public Option<V> get (K k) {
//        int hc = computeHash (k);
//        return Option.makeOption ((V)lookuphc (k, hc));
//    }

	final public V get(Object k) {
		return lookup((K) k);
	}

	final public Option<V> putOpt(Object key, Object value) {
		int hc = computeHash((K) key);
		return insertifhc((K) key, hc, (V) value, null);
	}

	@Override
	final public V put(Object key, Object value) {
		ensureReadWrite();
		int hc = computeHash((K) key);
		Option<V> ov = insertifhc((K) key, hc, (V) value, null);
		if (ov instanceof Some) {
			Some<V> sv = (Some<V>) ov;
			return sv.get();
		} else
			return null;
	}

	final public void update(K k, V v) {
		int hc = computeHash(k);
		inserthc(k, hc, v);
	}

	final public TrieMap<K, V> add(K k, V v) {
		update(k, v);
		return this;
	}

	final Option<V> removeOpt(K k) {
		int hc = computeHash(k);
		return removehc(k, null, hc);
	}

	@Override
	final public V remove(Object k) {
		ensureReadWrite();
		int hc = computeHash((K) k);
		Option<V> ov = removehc((K) k, null, hc);
		if (ov instanceof Some) {
			Some<V> sv = (Some<V>) ov;
			return sv.get();
		} else
			return null;
	}

//    final public TrieMap<K, V> remove (Object k) {
//        removeOpt ((K)k);
//        return this;
//    }

	final public Option<V> putIfAbsentOpt(K k, V v) {
		int hc = computeHash(k);
		return insertifhc(k, hc, v, INode.KEY_ABSENT);
	}

	@Override
	final public V putIfAbsent(Object k, Object v) {
		ensureReadWrite();
		int hc = computeHash((K) k);
		Option<V> ov = insertifhc((K) k, hc, (V) v, INode.KEY_ABSENT);
		if (ov instanceof Some) {
			Some<V> sv = (Some<V>) ov;
			return sv.get();
		} else
			return null;
	}

	@Override
	public boolean remove(Object k, Object v) {
		ensureReadWrite();
		int hc = computeHash((K) k);
		return removehc((K) k, (V) v, hc).nonEmpty();
	}

	@Override
	public boolean replace(K k, V oldvalue, V newvalue) {
		ensureReadWrite();
		int hc = computeHash(k);
		return insertifhc(k, hc, newvalue, oldvalue).nonEmpty();
	}

	public Option<V> replaceOpt(K k, V v) {
		int hc = computeHash(k);
		return insertifhc(k, hc, v, INode.KEY_PRESENT);
	}

	@Override
	public V replace(Object k, Object v) {
		ensureReadWrite();
		int hc = computeHash((K) k);
		Option<V> ov = insertifhc((K) k, hc, (V) v, INode.KEY_PRESENT);
		if (ov instanceof Some) {
			Some<V> sv = (Some<V>) ov;
			return sv.get();
		} else
			return null;
	}

	/***
	 * Return an iterator over a TrieMap.
	 * 
	 * If this is a read-only snapshot, it would return a read-only iterator.
	 * 
	 * If it is the original TrieMap or a non-readonly snapshot, it would return an
	 * iterator that would allow for updates.
	 * 
	 * @return
	 */
	public Iterator<Map.Entry<K, V>> iterator() {
		if (!nonReadOnly())
			return readOnlySnapshot().readOnlyIterator();
		else
			return new TrieMapIterator<K, V>(0, this);
	}

	/***
	 * Return an iterator over a TrieMap. This is a read-only iterator.
	 * 
	 * @return
	 */
	public Iterator<Map.Entry<K, V>> readOnlyIterator() {
		if (nonReadOnly())
			return readOnlySnapshot().readOnlyIterator();
		else
			return new TrieMapReadOnlyIterator<K, V>(0, this);
	}

	private int cachedSize() {
		INode<K, V> r = RDCSS_READ_ROOT();
		return r.cachedSize(this);
	}

	public int size() {
		if (nonReadOnly())
			return readOnlySnapshot().size();
		else
			return cachedSize();
	}

	String stringPrefix() {
		return "TrieMap";
	}

	/***
	 * This iterator is a read-only one and does not allow for any update operations
	 * on the underlying data structure.
	 * 
	 * @param <K>
	 * @param <V>
	 */
	private static class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
		TrieMapReadOnlyIterator(int level, final TrieMap<K, V> ct, boolean mustInit) {
			super(level, ct, mustInit);
		}

		TrieMapReadOnlyIterator(int level, TrieMap<K, V> ct) {
			this(level, ct, true);
		}

		void initialize() {
			assert (ct.isReadOnly());
			super.initialize();
		}

		public void remove() {
			throw new UnsupportedOperationException("Operation not supported for read-only iterators");
		}

		Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
			// Return non-updatable entry
			return rr;
		}
	}

	private static class TrieMapIterator<K, V> implements java.util.Iterator<Map.Entry<K, V>> {
		private int level;
		protected TrieMap<K, V> ct;
		private final boolean mustInit;
		private BasicNode[][] stack = new BasicNode[7][];
		private int[] stackpos = new int[7];
		private int depth = -1;
		private Iterator<Map.Entry<K, V>> subiter = null;
		private KVNode<K, V> current = null;
		private Map.Entry<K, V> lastReturned = null;

		TrieMapIterator(int level, final TrieMap<K, V> ct, boolean mustInit) {
			this.level = level;
			this.ct = ct;
			this.mustInit = mustInit;
			if (this.mustInit)
				initialize();
		}

		TrieMapIterator(int level, TrieMap<K, V> ct) {
			this(level, ct, true);
		}

		public boolean hasNext() {
			return (current != null) || (subiter != null);
		}

		public Map.Entry<K, V> next() {
			if (hasNext()) {
				Map.Entry<K, V> r = null;
				if (subiter != null) {
					r = subiter.next();
					checkSubiter();
				} else {
					r = current.kvPair();
					advance();
				}

				lastReturned = r;
				return r != null ? nextEntry(r) : null;
			} else {
				// return Iterator.empty ().next ();
				return null;
			}
		}

		Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
			return new Map.Entry<K, V>() {
				private V updated = null;

				@Override
				public K getKey() {
					return rr.getKey();
				}

				@Override
				public V getValue() {
					return (updated == null) ? rr.getValue() : updated;
				}

				@Override
				public V setValue(V value) {
					updated = value;
					return ct.replace(getKey(), value);
				}

				@Override
				public String toString() {
					return "TrieMapIterator[hash=" + MathUtil.toHex(super.hashCode()) + ",key=" + getKey() + ",value=" + getValue() + "]";
				}
			};
		}

		private void readin(INode<K, V> in) {
			MainNode<K, V> m = in.gcasRead(ct);
			if (m instanceof CNode) {
				CNode<K, V> cn = (CNode<K, V>) m;
				depth += 1;
				stack[depth] = cn.array;
				stackpos[depth] = -1;
				advance();
			} else if (m instanceof TNode) {
				current = (TNode<K, V>) m;
			} else if (m instanceof LNode) {
				subiter = ((LNode<K, V>) m).listmap.iterator();
				checkSubiter();
			} else if (m == null) {
				current = null;
			}
		}

		// @inline
		private void checkSubiter() {
			if (!subiter.hasNext()) {
				subiter = null;
				advance();
			}
		}

		// @inline
		void initialize() {
//            assert (ct.isReadOnly ());
			INode<K, V> r = ct.RDCSS_READ_ROOT();
			readin(r);
		}

		void advance() {
			if (depth >= 0) {
				int npos = stackpos[depth] + 1;
				if (npos < stack[depth].length) {
					stackpos[depth] = npos;
					BasicNode elem = stack[depth][npos];
					if (elem instanceof SNode) {
						current = (SNode<K, V>) elem;
					} else if (elem instanceof INode) {
						readin((INode<K, V>) elem);
					}
				} else {
					depth -= 1;
					advance();
				}
			} else
				current = null;
		}

		protected TrieMapIterator<K, V> newIterator(int _lev, TrieMap<K, V> _ct, boolean _mustInit) {
			return new TrieMapIterator<K, V>(_lev, _ct, _mustInit);
		}

		protected void dupTo(TrieMapIterator<K, V> it) {
			it.level = this.level;
			it.ct = this.ct;
			it.depth = this.depth;
			it.current = this.current;

			// these need a deep copy
			System.arraycopy(this.stack, 0, it.stack, 0, 7);
			System.arraycopy(this.stackpos, 0, it.stackpos, 0, 7);

			// this one needs to be evaluated
			if (this.subiter == null)
				it.subiter = null;
			else {
				List<Map.Entry<K, V>> lst = toList(this.subiter);
				this.subiter = lst.iterator();
				it.subiter = lst.iterator();
			}
		}

		// /** Returns a sequence of iterators over subsets of this iterator.
		// * It's used to ease the implementation of splitters for a parallel
		// version of the TrieMap.
		// */
		// protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
		// null) {
		// // the case where an LNode is being iterated
		// val it = subiter
		// subiter = null
		// advance()
		// this.level += 1
		// Seq(it, this)
		// } else if (depth == -1) {
		// this.level += 1
		// Seq(this)
		// } else {
		// var d = 0
		// while (d <= depth) {
		// val rem = stack(d).length - 1 - stackpos(d)
		// if (rem > 0) {
		// val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
		// stack(d) = arr1
		// stackpos(d) = -1
		// val it = newIterator(level + 1, ct, false)
		// it.stack(0) = arr2
		// it.stackpos(0) = -1
		// it.depth = 0
		// it.advance() // <-- fix it
		// this.level += 1
		// return Seq(this, it)
		// }
		// d += 1
		// }
		// this.level += 1
		// Seq(this)
		// }

		private List<Entry<K, V>> toList(Iterator<Entry<K, V>> it) {
			ArrayList<Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
			while (it.hasNext()) {
				list.add(it.next());
			}
			return list;
		}

		void printDebug() {
			System.out.println("ctrie iterator");
			System.out.println(Arrays.toString(stackpos));
			System.out.println("depth: " + depth);
			System.out.println("curr.: " + current);
			// System.out.println(stack.mkString("\n"));
		}

		@Override
		public void remove() {
			if (lastReturned != null) {
				ct.remove(lastReturned.getKey());
				lastReturned = null;
			} else
				throw new IllegalStateException();
		}

	}

	/** Only used for ctrie serialization. */
	// @SerialVersionUID(0L - 7237891413820527142L)
	private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;

	public boolean containsKey(Object key) {
		if (key == null)
			return false;
		return lookup((K) key) != null;
	}

	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		return entrySet;
	}

	/***
	 * Support for EntrySet operations required by the Map interface
	 *
	 */
	final class EntrySet extends AbstractSet<Map.Entry<K, V>> {

		@Override
		public Iterator<Map.Entry<K, V>> iterator() {
			return TrieMap.this.iterator();
		}

		@Override
		public final boolean contains(final Object o) {
			if (!(o instanceof Map.Entry)) {
				return false;
			}
			final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
			final K k = e.getKey();
			final V v = lookup(k);
			return v != null;
		}

		@Override
		public final boolean remove(final Object o) {
			if (!(o instanceof Map.Entry)) {
				return false;
			}
			final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
			final K k = e.getKey();
			return null != TrieMap.this.remove(k);
		}

		@Override
		public final int size() {
			int size = 0;
			for (final Iterator<?> i = iterator(); i.hasNext(); i.next()) {
				size++;
			}
			return size;
		}

		@Override
		public final void clear() {
			TrieMap.this.clear();
		}
	}

	private void readObject(ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
		inputStream.defaultReadObject();
		this.root = INode.newRootNode();

		final boolean ro = inputStream.readBoolean();
		final int size = inputStream.readInt();
		for (int i = 0; i < size; ++i) {
			final K key = (K) inputStream.readObject();
			final V value = (V) inputStream.readObject();
			add(key, value);
		}

		// Propagate the read-only bit
		try {
			READONLY_FIELD.setBoolean(this, ro);
		} catch (IllegalAccessException e) {
			throw new IOException("Failed to set read-only flag", e);
		}
	}

	private void writeObject(ObjectOutputStream outputStream) throws IOException {
		outputStream.defaultWriteObject();

		final Map<K, V> ro = readOnlySnapshot();
		outputStream.writeBoolean(isReadOnly());
		outputStream.writeInt(ro.size());

		for (Entry<K, V> e : ro.entrySet()) {
			outputStream.writeObject(e.getKey());
			outputStream.writeObject(e.getValue());
		}
	}
}
